package com.lxm.algorithm.tree.binaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BinaryTree {
	/*
	 * ���ɶ�����
	 */
	public void createBinaryTree(BinaryTreeNode root){
		Scanner scan=new Scanner(System.in);
		String str=scan.next();
		if(str.equals("#")){
			root=null;
		}else{
			root.setData(str);
			//����������
			root.setLeftChild(new BinaryTreeNode());
			createBinaryTree(root.getLeftChild());
			//����������
			root.setRightChild(new BinaryTreeNode());
			createBinaryTree(root.getRightChild());
		}
	}
	
	/**
	 * ǰ������
	 */
	public void preOrderTraverse(BinaryTreeNode root){
		if(root!=null&&root.getData()!=null){
			System.out.print(root.getData()+" ");
			preOrderTraverse(root.getLeftChild());
			preOrderTraverse(root.getRightChild());
		}
	}

	/**
	 * 非递归先根遍历二叉树
	 * @param root
	 */
	public void preOrderLoop(BinaryTreeNode root) {
		if (root == null) {
			return;
		}
		Stack<BinaryTreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			BinaryTreeNode node = stack.pop();
			System.out.print(node.getData()+" ");
			if (node.getRightChild() != null) {
				stack.push(node.getRightChild());
			}
			if (node.getLeftChild() != null) {
				stack.push(node.getLeftChild());
			}
		}
	}


	/**
	 * �и�����
	 */
	public void inOrderTraverse(BinaryTreeNode root){
		if(root!=null&&root.getData()!=null){
			inOrderTraverse(root.getLeftChild());
			System.out.print(root.getData()+" ");
			inOrderTraverse(root.getRightChild());
		}
	}

	/**
	 * 非递归中序遍历
	 *
	 * @param root
	 */
	public void inOrderLoop(BinaryTreeNode root) {
		if (root == null) {
			return;
		}
		BinaryTreeNode cur = root;
		Stack<BinaryTreeNode> stack = new Stack<>();
		while (cur != null || !stack.isEmpty()) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.getLeftChild();
			} else {
				cur = stack.pop();
				System.out.print(cur.getData() + " ");
				cur = cur.getRightChild();
			}
		}
	}

	/**
	 * �������
	 */
	public void postOrderTraverse(BinaryTreeNode root){
		if(root!=null&&root.getData()!=null){
			postOrderTraverse(root.getLeftChild());
			postOrderTraverse(root.getRightChild());
			System.out.print(root.getData()+" ");
		}
	}

	/**
	 * 非递归后序遍历
	 *
	 * @param root
	 */
	public void postOrderLoop(BinaryTreeNode root) {
		if (root == null) {
			return;
		}
		Stack<BinaryTreeNode> stack1 = new Stack<>();
		Stack<BinaryTreeNode> stack2 = new Stack<>();
		stack1.push(root);
		while (!stack1.isEmpty()) {
			BinaryTreeNode n = stack1.pop();
			stack2.push(n);
			if (n.getLeftChild() != null) {
				stack1.push(n.getLeftChild());
			}
			if (n.getRightChild() != null) {
				stack1.push(n.getRightChild());
			}
		}
		while (!stack2.isEmpty()) {
			System.out.print(stack2.pop().getData() + " ");
		}
	}

	/**
	 * �ø��ڵ�����У�
	 * ���ڵ���������ӽڵ�����У������в�Ϊ��ʱ����ѭ��
	 * �������
	 */
	public void levelOrderTraverse(BinaryTreeNode root){
		//����һ��queue
		Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
		queue.offer(root);
		while(!queue.isEmpty()){
			BinaryTreeNode temp=queue.poll();
			System.out.print(temp.getData()+" ");
			//���������ڵ������ڵ������
			if(temp.getLeftChild()!=null&&temp.getLeftChild().getData()!=null){
				queue.offer(temp.getLeftChild());
			}
			//��������ҽڵ������ڵ������
			if(temp.getRightChild()!=null&&temp.getRightChild().getData()!=null){
				queue.offer(temp.getRightChild());
			}
		}
	}

	public static void main(String[] args){
		BinaryTreeNode node1 = new BinaryTreeNode("3", null, null);
		BinaryTreeNode node2 = new BinaryTreeNode("4", null, null);
		BinaryTreeNode node3 = new BinaryTreeNode("6", null, null);
		BinaryTreeNode node4 = new BinaryTreeNode("7", null, null);
		BinaryTreeNode node5 = new BinaryTreeNode("2", node1, node2);
		BinaryTreeNode node6 = new BinaryTreeNode("5", node3, node4);
		BinaryTreeNode root = new BinaryTreeNode("1", node5, node6);
		BinaryTree tree = new BinaryTree();
		tree.preOrderTraverse(root);
		System.out.println("\n----------------------------------");
		tree.preOrderLoop(root);
		System.out.println("\n----------------------------------");
		tree.inOrderTraverse(root);
		System.out.println("\n----------------------------------");
		tree.inOrderLoop(root);
		System.out.println("\n----------------------------------");
		tree.postOrderTraverse(root);
		System.out.println("\n----------------------------------");
		tree.postOrderLoop(root);
	}
	
}
